Traditionally, software applications such as word processors create page-based documents where each page contains graphic objects such as text, lines, fill regions and image data. When representing the document data on a display device or a printing device, such software applications typically send commands defined in terms of the graphics interface services of a native operating system within which the software application operates.
One such operating system is Microsoft Windows™, which has graphics interface services typically known as the graphics device interface (GDI) layer. The GDI layer is generally an application programming interface (API) providing a rich set of graphics features to all applications. Typically, a graphics rendering system renders the graphics objects received from the GDI layer, generating pixels which are then sent to a target device for storage, display, or printing. Rendering is the process by which the graphics objects received from the GDI layer are converted to pixels by the graphics rendering system.
The graphics rendering system may, at times, be requested to render a page at 90, 180, or 270 degrees rotation, as illustrated in FIGS. 3A to 3D.
There are various reasons why a page may be rotated from the original data. A printer may be limited regarding the orientation of a printed page. If a printer is only capable of printing an A4 portrait page, then a page created in A4 landscape needs to be rotated before the page can be printed. Also, a user may request a specific page rotation based on his/her requirements. Typically, modern day printer drivers allow a user to create output formats for special purposes. Such formats include birthday cards, n-up pages (multiple pages scaled to fit on the one page), double-sided pages, letters, cards and even books.
For example, FIG. 4A shows a rendering 400 of the page 300 of FIG. 3A using 4 pages per sheet, two of the renderings (marked page 2 and page 3) being rotated by 180 degrees. Page 400 may be folded in half along Fold 1 401 and then folded again along Fold 2 402 to form a “card” that has four upright renderings on it. The resulting card can be seen in FIGS. 4B and 4C.
In such cases, original data passed by the GDI layer needs to be transformed by the graphics rendering system and then rendered according to the specific format requested by the user. Often such formats require page data to be rotated at a specific angle to produce the final output.
To rotate a page containing graphics objects, each object on a page is rotated by a specified angle. The page boundary may also be rotated depending on the final output requirement. FIGS. 3B, 3C and 3D show renderings of the example page 300 of FIG. 3A, rotated 90, 180 and 270 degrees respectively. It may not always be necessary to rotate a page. For example, there is no use in rotating FIG. 3A to produce FIG. 3C when printing. However, such inversion may be useful when rendering the page 300 to a screen. There are also circumstances where the objects on the page are to be rotated but the page itself is not. An example of this is shown in FIG. 3E, where the page boundary is the same as that of page 300, but the data is printed 2-up with each of the two renderings rotated by 90 degrees.
An object boundary is typically described by a path made up of a number of points. Since this path is described as a continuous entity, using a defined point system, these continuous paths must be resolved into discrete pixel values at the rendering stage. Typically, paths are broken up and dealt with in monotonically increasing order. A variety of rules are available to resolve a continuous path into its equivalent discrete format. These rules are typically known as pixelization rules. A couple of well known pixelization rules are the GDI pixelization rule and the PostScript pixelization rule. The GDI pixelization rule uses the Grid Intersection Quantization rule in order to determine which pixels are activated by a path.
Representing a continuous signal, i.e. a path defined as a set of points, with a discrete approximation causes errors to be introduced in representing a final pixelized object. Typically, there are problems representing very small objects as the paths themselves are not discrete, but their final representation must be, so much of the original “signal” is lost in the digital conversion. Also, since pixelization rules typically do not take the rotation of an object into account, any shift or arbitration required to resolve a path into a pixel is typically not rotation invariant. That is, if a path is rendered at 90 degrees, and the same path is rendered at 180 degrees, then it is unlikely that the same set of pixels is turned on for each of the rendered paths.
Traditionally, there are a number of ways of accurately rendering an object to be rotated. The most basic method is to render the object with no rotation to produce pixel data and then to rotate the rendered pixel data. Since the original path has been quantized, the rotated version will be pixel accurate. However, this method requires large amounts of memory and CPU resources for a full page and is slow if done on an object-per-object basis.
Another method used to produce pixel-accurate rotations is to produce the pixedges of a path (pixedges are the edges of each pixel) and then rotate the pixedges. Since the pixedges define the exact boundary of the object to be rendered, the same pixels will be filled regardless of the rotation of the objects. This method is very cumbersome, since each edge defines a pixel boundary, and consequently the path data for the entire set of edges defining the boundary of an object may be huge. Compared with the original points of the path, the pixedge data uses more memory and typically takes more time to rotate. Rendering objects in such a manner is expensive in terms of CPU resources consumed.
An example is shown in FIGS. 5A-C. The object 500 shown in FIG. 5A has an object boundary 501 as shown in FIG. 5B. FIG. 5C shows a quantized path 502 derived from the boundary 501. The path 502 can be accurately rotated since it has been quantized. However, where the original path 501 only has 7 points, the quantized version 502 has 31 points. Clearly, rotating many such quantized objects would consume a large amount of CPU resources.
In some known graphic rendering systems, rendering is a two-stage process. In these rendering systems, graphics objects are first converted into an intermediate language before the rendering process begins. This intermediate form, containing all the converted graphic objects, is known as a display list. In one such system, the first stage of the process converts each graphic object received from the GDI layer into an intermediate edge-based object graphics format, such that all edges are sorted in ascending y-order, then ascending x-order. The x and y axes correspond respectively to the scan lines and pixel locations on such scan lines in a rasterized display. The output from the first stage is typically a display list of edges and their associated fill priority (z-order), along with other information such as whether an edge is a clipping edge or a filling edge. The output from the first stage is sometimes called a job. The job contains all the information needed by the second stage to render the page.
The second stage of the process involves a rendering module parsing the job and generating the pixels for the output device for each scanline down the page.
For renderers that use such a two-stage approach in which information is stored in an intermediate form, each object has to be converted to the intermediate form. However, it is often the case that not all the objects stored in the display list will actually be part of the rendered output. For example, the second stage of the rendering system may only be asked to render a specific part of a page, or the objects that are stored in the intermediate format may actually lie on and/or outside the bounds of the page. These cases represent a problem for edge-based renderers because the edges of the objects that lie outside the region to be rendered still need to be tracked. Such edges that lie outside the region to be rendered need to be tracked because they may enter the region to be rendered. Edges are typically tracked scanline by scanline, and thus tracking such objects can be time consuming and greatly slow the performance of the renderer.
There are a couple of methods used to deal with objects that do not lie within the region to be rendered. The first method is the simplest, and simply involves tracking the edges of all objects in the display list and only rendering pixel data when the edges are within the region to be rendered. Another method is to clip all objects to the current rendering boundary. This involves tracing a path in and out of the region to be rendered and clipping any part of the path that lies outside the region to be rendered. This task is not trivial and requires precious CPU resources to trace a path and determine the points that lie outside the area to be rendered. Furthermore, if another part of the page needs to be rendered, a new display list has to be constructed. Also, because an object boundary is represented by edges that typically use a fixed format to represent the edge position, accuracy problems can arise when clipping the boundary. For example, consider the line joining the two points, (0, −4) and (55¾, 56). This line crosses the x-axis at about 3.72. If this line is clipped to the x-axis and the accuracy of the points of the line is limited to 1/16, then 3.6875 would replace 3.72. Hence, accuracy has been lost in the clipping of the line. This loss in accuracy can lead to distortion of the final rendered output of an object.
Another problem with edge-based renderers lies in the speed of updating edges for the next scanline. This is because the x position of each edge needs to be updated to the next scanline according to the dx value of an edge. The updating of the edge also depends on the type of edge, further increasing the complexity of updating the edges. Typically, as each edge on a scanline is encountered, an edge update function is called. This function takes the current position of the edge, determines the real x position for the next scanline, and then determines the integer position for the next scanline. Typically, pages to be printed contain thousands of edges, and each of these edges must be updated by calling the update function for every scanline on which the edge is active. This represents a major part of the rendering time in a two-stage edge rendering system. Current methods used to update edges involve calling one update function that updates an edge according to its type. The problem with the approach is that every time an edge is updated the code must branch according to the edge type, which results in a slow method.
Another method of updating edges is to have a specific update function associated with each edge (using a function pointer). When an edge is to be updated the renderer can simply call the function according to the edge's function pointer. In this case the renderer only needs to set the function pointer once for each edge, and not every scanline, so the branching problems presented above are removed. However, each of these edge functions must be called whenever an edge is updated, so there are still large function call overheads, ultimately restricting the rendering speed.
It is an object of the present invention to overcome or at least ameliorate one or more aspects of the prior art.